package _2022.hot100._34_在排序数组中查找元素的第一个和最后一个位置;

import java.util.Arrays;


/**
 * @author： YHSimon
 * @date： 2022-04-08 20:30
 */
public class Solution {

    //O(logN)
    public int[] searchRange2(int[] nums,int target){
        int leftIdx=binarySearch(nums, target);
        int rightIdx=binarySearch(nums, target)-1;
        if(leftIdx<=rightIdx&&nums[leftIdx]==target){
            return new int[]{leftIdx,rightIdx};
        }
        return new int[]{-1,-1};
    }

    //第一个大于target的数的下标
    public int binarySearch(int[] nums,int target){
        int left=0,right=nums.length-1,ans=nums.length;
        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]>target){
                right =mid-1;
                ans=mid;
            }else{
                left=mid+1;
            }
        }
        return ans;
    }



    //o(N)  0ms
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) {
            return new int[]{-1, -1};
        }
        if (n == 1) {
            return nums[0] == target ? new int[]{0, 0} : new int[]{-1, -1};
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (target == nums[mid]) {
                int start = mid, end = mid;
                while (start - 1 >= 0 && nums[start - 1] == target) {
                    start--;
                }
                while (end + 1 <= n - 1 && nums[end + 1] == target) {
                    end++;
                }
                return new int[]{start, end};
            }
            if (target > nums[mid]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 6)));
    }
}
